# 定义结点
class Node(object):
    def __init__(self, item):
        self.item = item
        self.left = None
        self.right = None

    def __str__(self):
        return str(self.item)


# 定义二叉树
class Tree(object):
    def __init__(self):
        # 初始化根结点
        self.root = Node("root")

    # 添加子节点
    def add(self, item):
        # 创建结点
        node = Node(item)
        # 如果二叉树为空, 把新结点当做root结点
        if self.root is None:
            self.root = node
        # 二叉树非空
        else:
            # 定义一个包含根结点的列表
            q = [self.root]
            while len(q) > 0:
                pop_node = q.pop(0)
                # 添加到左子树
                if pop_node.left is None:
                    pop_node.left = node
                    return
                # 添加到右子树
                elif pop_node.right is None:
                    pop_node.right = node
                    return
                # 如果根结点左右子树都存在, 把左右子树加入列表, 继续循环遍历
                else:
                    q.append(pop_node.left)
                    q.append(pop_node.right)

    def breadh_travel(self):
        """广度优先遍历"""
        if self.root is None:
            return
        queue = []
        queue.append(self.root)
        while len(queue) > 0:
            pop_node = queue.pop(0)
            print(pop_node.item, end=" ")
            if pop_node.left:
                queue.append(pop_node.left)
            if pop_node:
                queue.append(pop_node.right)

    # 查找父节点
    def get_parent(self, item):
        # 根结点没有父节点
        if self.root.item == item:
            return None
        tmp = [self.root]
        while tmp:
            pop_node = tmp.pop(0)
            # 左子树为传入结点
            if pop_node.left and pop_node.left.item == item:
                return pop_node
            # 右子树为传入结点
            elif pop_node.right and pop_node.right.item == item:
                return pop_node
            # 如果存在, 把左子树和右子树加入列表, 继续新的循环
            else:
                if pop_node.left is not None:
                    tmp.append(pop_node.left)
                if pop_node.right is not None:
                    tmp.append(pop_node.right)
        return None

    # 删除结点
    def delete(self, item):
        # 空二叉树, 无法删除
        if self.root is None:
            return False
        # 调用get_parent方法, 获取要删除结点的父节点
        parent = self.get_parent(item)
        # 如果父节点存在
        if parent:
            # 判断要删的是父节点的左孩子还是右孩子
            del_node = parent.left if parent.left.item == item else parent.right
            # 左子树不存在, 右子树也不存在
            if del_node.left is None and del_node.right is None:
                # 直接删除
                del del_node
                return True
            # 左子树不存在, 右子树存在
            elif del_node.left is None:
                # 要删除的是左孩子
                if parent.left.item == item:
                    # 右子树顶替删除的子节点成为新的左孩子
                    parent.left = del_node.right
                # 要删除的是右孩子
                else:
                    # 右子树顶替删除的子节点成为新的右孩子
                    parent.right = del_node.right
                # 删除结点
                del del_node
                return True
            # 左子树存在, 右子树不存在
            elif del_node.right is None:
                # 要删除的是左孩子
                if parent.left.item == item:
                    # 左子树顶替删除结点成为新的左孩子
                    parent.left = del_node.left
                # 要删除的是右孩子
                else:
                    # 左子树顶替删除结点成为新的右孩子
                    parent.right = del_node.left
                # 删除节点
                del del_node
                return True
            # 左子树存在, 右子树也存在
            else:
                # 要删除的结点
                tmp_pre = del_node
                # 要删除结点的右子树
                tmp_next = del_node.right
                # 寻找右子树的最左叶子结点, 替换要删除的结点
                # 右子树的左子树为空
                if tmp_next.left is None:
                    # 老的右子树的右子树==>老的右子树
                    tmp_pre.right = tmp_next.right
                    # 老的左子树==>老的右子树的左子树
                    tmp_next.left = del_node.left
                    # 老的右子树==>老的右子树的右子树
                    tmp_next.right = del_node.right
                # 右子树的左子树非空
                else:
                    # 找最左, 只有还有左子树就向上
                    while tmp_next.left:
                        tmp_pre = tmp_next
                        tmp_next = tmp_next.left
                    # 替代
                    tmp_pre.left = tmp_next.right
                    tmp_next.left = del_node.left
                    tmp_next.right = del_node.right
                    # 如果待删除节点是父节点的左孩子
                if parent.left.item == item:
                    parent.left = tmp_next
                    # 如果待删除节点是父节点的右孩子
                else:
                    parent.right = tmp_next
                del del_node
                return True
        else:
            return False




